Paul Gardner Allen sinh tại Seattle, Washington trong gia đình Kenneth S. Allen, phó giám đốc của thư viện trường Đại học Washington, và Faye G. Allen, vào năm 1953. Allen học tại Lakeside School, một ngôi trường tư thục uy tín ở Seattle, và kết bạn với Gates, người học dưới ông hai lớp nhưng chia sẻ lòng đam mê máy tính với nhau. Allen là một học sinh gương mẫu ở Lakeside School. Họ đã sử dụng máy điện báo của trường để phát triển kỹ năng lập trình trên vài hệ thống máy chia sẻ thời gian. Sau khi tốt nghiệp, Allen nhập học tại trường Đại học Tiểu bang Washington, và là một thành viên tích cực của Phi Kappa Theta Fraternity, mặc dù ông bỏ học sau đó hai năm để làm lập trình viên cho Honeywell ở Boston, ở đó ông gặp lại người bạn cũ. Sau đó ông đã thuyết phục Gates bỏ học ở trường Đại học Harvard để thành lập Microsoft.